﻿using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Acoris.Foundation
{
    /// <summary>
    /// 表示朴素trie-tree数据结构
    /// </summary>
    [DebuggerDisplay("count:{Count}")]
    public sealed partial class PlainTrieTree
    {
        private const string ArgumentNullExceptionContent  = "参数不能为空";
        private const string InvalidOperationExceptionContent = "不能添加自身到字典之中";
        private const string ActionNullContent = "字典中不允许存在空委托";
        private const string KeyNotFoundExceptionContent = "指定的键不在集合之中";

        #region Node Definition

        /// <summary>
        /// 声明PlainTrieTree的节点结构
        /// </summary>
        internal sealed class Node
        {
            #region Constructor

            /// <summary>
            /// 初始化根节点
            /// </summary>
            internal Node() : this(char.MinValue) { }

            /// <summary>
            /// 使用指定的值初始化节点
            /// </summary>
            /// <param name="value"></param>
            internal Node(char value)
            {
                this.value = value;
                this.next = new Dictionary<char, Node>();
                this.key = new List<char>();
            }

            #endregion

            #region Fields

            // 表示当前位置是否结束
            internal bool ended;

            // 表示后继的子节点
            private Dictionary<char,Node> next;

            private List<char> key;

            // 当前节点的值
            internal char value;

            internal Action action;

            #endregion

            #region Method

            /// <summary>
            /// 设置当前节点的后继节点的值
            /// </summary>
            /// <param name="value">后继节点的键</param>
            /// <param name="nextNode">后继节点的值</param>
            internal void SetNode(char value, Node nextNode) {
                if (nextNode == null) {
                    throw new ArgumentNullException(ArgumentNullExceptionContent);
                }
                if (nextNode == this) {
                    throw new InvalidOperationException();
                }
                next.Add(value, nextNode);
                key.Add(value);
            }

            /// <summary>
            /// 
            /// </summary>
            /// <param name="value"></param>
            internal void RemoveNode(char value)
            {
                next.Remove(value);
                key.Remove(value);
            }

            /// <summary>
            /// 
            /// </summary>
            /// <returns></returns>
            internal Node Clone()
            {
                var newDictionary = new Dictionary<char, Node>(next);
                return new Node
                {
                    next = newDictionary,
                    action = action,
                    ended = ended,
                    value = value
                };
            }

            /// <summary>
            /// 
            /// </summary>
            /// <param name="index"></param>
            /// <returns></returns>
            internal Node GetNextNode(int index)
            {
                var keys = key[index];
                return next[keys];
            }

            /// <summary>
            /// 尝试获得后继节点
            /// </summary>
            /// <param name="value"></param>
            /// <returns></returns>
            internal Node GetNextNode(char value)
            {
                if (next.ContainsKey(value)) {
                    return next[value];
                }
                return null;
            }

            internal bool HasNextState {
                get { return next.Count > 0; }
            }

            /// <summary>
            /// 
            /// </summary>
            internal void Clear()
            {
                if (next.Count == 0) {
                    return;
                }
                else {
                    foreach (var node in next) {
                        node.Value.Clear();
                    }
                    next.Clear();
                    action = null;
                }
            }

            /// <summary>
            /// 获取一个值该值指示指定的后继状态是否存在
            /// </summary>
            /// <param name="value"></param>
            /// <returns></returns>
            internal bool ContainKey(char value)
            {
                return next.ContainsKey(value);
            }

            #endregion


            /// <summary>
            /// 
            /// </summary>
            /// <returns></returns>
            public override string ToString()
            {
                if (value == char.MinValue) {
                    return "root";
                }
                return value.ToString();
            }

            /// <summary>
            /// 
            /// </summary>
            internal int Count {
                get {
                    return next.Count;
                }
            }

        }

        #endregion

        #region Fields

        internal Node root;
        private int m_count;

        #endregion

        public PlainTrieTree()
        {
            root = new Node();
        }

        #region Method

        /// <summary>
        /// 将指定的字符串添加到前缀树
        /// </summary>
        /// <param name="text"></param>
        public void AppendString(string text, Action action)
        {
            lock (m_lock) {
                Append(text, action);
            }
        }

        // 将指定的字符串添加到前缀树，当前操作非线程安全
        // 算法复杂度:O(N)，N为字符串的长度
        void Append(string text, Action action)
        {
            if (action == null) {
                throw new ArgumentNullException(ActionNullContent);
            }

            var node = this.root;
            var offset = 0;
            var failedTime = 0;
            foreach (var input in text) {
                if (!node.ContainKey(input)) {
                    var newNode = new Node(input);
                    node.SetNode(input, newNode);
                }
                else {
                    failedTime++;
                }
                node = node.GetNextNode(input);
            }

            if (failedTime != text.Length) {
                node.ended = true;
                m_count++;
                node.action = action;
            }
            offset++;
        }

        /// <summary>
        /// 在指定的前缀树中删除指定的字符串
        /// </summary>
        /// <param name="text"></param>
        public void RemoveString(string text)
        {
            lock (m_lock) {
                Remove(text);
            }
        }

        // 移除指定的字符串，该操作非线程安全
        // 算法复杂度:O(N)，N为字符串的长度
        void Remove(string text)
        {
            var node = root;
            var stack = new Stack<Node>();
            // Remove(node, text, 0);
            // 使用非递归方式
            node = MoveToLast(text, node, 0,stack);
            RemoveTagOrTrace(stack);
            m_count--;
        }

        void RemoveTagOrTrace(Stack<Node> nodeStack)
        {
            var IsMeetFirstEndedTag = false;
            var NeedClearLast = false;
            var key = char.MinValue;

            foreach(var node in nodeStack) {
                if (NeedClearLast) {
                    NeedClearLast = false;
                    node.RemoveNode(key);
                }

                if(node.ended && !IsMeetFirstEndedTag) {
                    IsMeetFirstEndedTag = true;
                    node.ended = false;
                }
                if (!node.HasNextState) {
                    NeedClearLast = true;
                    key = node.value;
                }
            }
        }

        // 遍历当前字典，直到到达字符串末端
        Node MoveToLast(string text, Node node, int index,Stack<Node> nodeStack)
        {
            nodeStack.Push(node);
            if (index == text.Length) {
                return node;
            }
            else {
                var element = text[index++];
                if (!node.ContainKey(element)) {
                    throw new KeyNotFoundException(KeyNotFoundExceptionContent);                    
                }
                return MoveToLast(text, node.GetNextNode(element), index,nodeStack);
            }
        }

        //// 递归方式删除节点
        //bool Remove(Node node,string input,int index)
        //{
        //    if(input.Length == index) {
        //        if (node.HasNextState) {
        //            node.ended = false;
        //        }
        //        return !node.HasNextState;
        //    }
        //    else {
        //        if (Remove(node.GetNextNode(input[index++]), input, index)) {
        //            node.RemoveNode(input[index - 1]);
        //        }
        //        return !node.ended;
        //    }
        //}


        /// <summary>
        /// 清空当前前缀树
        /// </summary>
        public void Clear()
        {
            lock (m_lock) {
                root.Clear();
            }           
        }

        #endregion

        /// <summary>
        /// 获取当前前缀树中的元素集合
        /// </summary>
        public int Count {
            get { return m_count; }
        }
    }
}
